package com.lxw.question;

import sun.applet.Main;

import java.util.*;

public class Q01 {
    /**
     * 题目描述
     *
     * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
     * 使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
     *
     * 注意：答案中不可以包含重复的三元组。
     * 题目来源：leetcode-cn.com.
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        /**
         * 解题思路
          1. 将数组进行排序
          2. 遍历每个元素执行以下操作
          3. 用两个指针，分别指向当前元素的下一位和数组尾
          4. 判断三数之和是否为零。若为零，则加入result（并且为了去重，需要判断l指针的下一位和r指针的前一位是否和当前指针相等）
          5. 之后对l++,r--,知道l<r不满足
          6. 若三数之和大于0，说明数太大了，需要r--
          7.若三数之和小于零，说明数太小了，需要l++.
         */
        List<List<Integer>> result = new LinkedList<>();
        //1.对数组进行排序
        Arrays.sort(nums);
        int len = nums.length;
        int l;
        int r;
        //特殊情况，陷阱测试数据
        if(len == 0 || len < 3)
            return result;

        for(int i = 0 ; i < len ; i++){
            //去重，如果当前元素和上个元素的值一样，则忽略，因为不会有什么结果的。
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            l =  i + 1;
            r = len - 1;
            //去重，当元素大于零，他后面不会有两个数的值和它相加之后等于零。因为这是按升序排列的。
            if(nums[i] > 0){
                break;
            }

            while(l < r){
                int value = nums[i] + nums[l] + nums[r];
                //结果等于零
                if(value == 0){
                    result.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    //去重，l++
                    while(l < r && nums[l] == nums[l+1])
                        l++;
                    while(l < r && nums[r] == nums[r-1])
                        r--;
                    l++;
                    r--;
                }
                //结果大于零
                if(value > 0){
                    r--;
                }
                if(value < 0){
                    l++;
                }
            }
        }
        return result;
    }

    public static void main(String[] args){
        int[] nums = {-2,-3,1,2,3,15,3,7,9,2};
        List<List<Integer>> result = threeSum(nums);
        for(List<Integer> l : result){
            System.out.println(l);
        }
    }


}
